package data_structure.offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class TreeNode {

    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

    public TreeNode() {

    }

    public ArrayList<Integer> preOrder(TreeNode node) {

        ArrayList<Integer> list = new ArrayList<>();

        list.add(node.value);
        if (node.left != null) {
            list.addAll(preOrder(node.left));
        }
        if (node.right != null) {
            list.addAll(preOrder(node.right));
        }
        return list;
    }

    public ArrayList<Integer> inOrder(TreeNode node) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        if (node.left != null) {
            list.addAll(inOrder(node.left));
        }
        list.add(node.value);

        if (node.right != null) {
            list.addAll(inOrder(node.right));
        }

        return list;
    }

    public ArrayList<Integer> postOrder(TreeNode node) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        if (node.left != null) {
            list.addAll(preOrder(node.left));
        }

        if (node.right != null) {
            list.addAll(preOrder(node.right));
        }
        list.add(node.value);

        return list;
    }

    public TreeNode reConstructTree(int[] pre, int[] in) {

        if (pre == null || in == null || in.length != pre.length || pre.length == 0) {
            return null;
        }

        TreeNode head = new TreeNode(pre[0]);
        int index = 0;
        while (index < in.length && in[index] != pre[0]) {
            index++;
        }

        head.left = reConstructTree(Arrays.copyOfRange(pre, 1, index + 1), Arrays.copyOfRange(in, 0, index));
        head.right = reConstructTree(Arrays.copyOfRange(pre, index + 1, pre.length), Arrays.copyOfRange(in, index + 1, in.length));
        return head;
    }

    public TreeNode reConstructBinaryTree2(int[] preorder, int[] inorder) {

        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
            return null;
        }

        return helper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] preorder, int preL, int preR, int[] inorder, int inL, int inR) {
        if (preL > preR || inL > inR) {
            return null;
        }
        int rootVal = preorder[preL];
        int index = 0;
        while (index <= inR && inorder[index] != rootVal) {
            index++;
        }
        TreeNode root = new TreeNode(rootVal);

        root.left = helper(preorder, preL + 1, preL - inL + index, inorder, inL, index);
        root.right = helper(preorder, preL - inL + index + 1, preR, inorder, index + 1, inR);
        return root;
    }

    public boolean hasSubTree(TreeNode source, TreeNode target) {

        if (target == null) {
            return false;
        }
        if (source == null) {
            return false;
        }

        if (doseTree1haveTree2(source, target)) {
            return true;
        }
        return hasSubTree(source.left, target) || hasSubTree(source.right, target);
    }

    public boolean doseTree1haveTree2(TreeNode source, TreeNode target) {

        if (source == null && target == null) {
            return true;
        }

        if (source == null || target == null) {
            return false;
        }

        if (source.value != target.value) {
            return false;
        }
        return doseTree1haveTree2(source.left, target.left) && doseTree1haveTree2(source.right, target.right);
    }

    public ArrayList<Integer> printTreeNodeFromTopToBottom(TreeNode root, boolean isRecursion) {
        if (root == null) {
            return null;
        }

        ArrayList<Integer> list = new ArrayList<Integer>();
        if (!isRecursion) {

            Queue<TreeNode> queue = new LinkedList<TreeNode>();

            queue.offer(root);

            while (!queue.isEmpty()) {

                TreeNode node = queue.poll();
                list.add(node.value);

                if (node.left != null) {
                    list.add(node.left.value);
                }

                if (node.right != null) {
                    list.add(node.right.value);
                }
            }
        } else {
            list.add(root.value);
            levelOrder(root, list);

        }
        return list;

    }

    private void levelOrder(TreeNode root, ArrayList<Integer> list) {

        if (root == null) {
            return;
        }
        if (root.left != null) {
            list.add(root.left.value);
        }
        if (root.right != null) {
            list.add(root.right.value);
        }
        levelOrder(root.left, list);
        levelOrder(root.right, list);
    }

    public boolean verifySequenceOfBST(int[] sequence) {

        if (sequence == null || sequence.length == 0) {
            return false;
        }

        int reStart = 0;
        int rootIndex = sequence.length - 1;
        for (int i = reStart; i < rootIndex; i++) {
            if (sequence[i] < sequence[rootIndex]) {
                reStart++;
            }
        }

        //所有的数都大于根节点
        if (reStart == 0) {
            verifySequenceOfBST(Arrays.copyOfRange(sequence, 0, rootIndex));
            return true;
        }

        //如果有重复的数据，返回false
        for (int i = reStart; i < rootIndex; i++) {
            if (sequence[i] <= sequence[rootIndex]) {
                return false;
            }
        }

        //递归遍历根节点左右子树
        verifySequenceOfBST(Arrays.copyOfRange(sequence, 0, reStart));
        verifySequenceOfBST(Arrays.copyOfRange(sequence, reStart, rootIndex));

        return true;
    }

    private ArrayList<ArrayList<Integer>> listAll = new ArrayList<>();
    private ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> findPath(TreeNode root, int target) {

        //root为null时，不考虑开始的情况，表示遍历完成
        if (root == null) {
            return listAll;
        }
        list.add(root.value);
        target -= root.value;
        //路径定义为从根节点开始到达最后的叶子
        if (target == 0 && root.left == null && root.right == null) {
            listAll.add(new ArrayList<>(list));
        }
        //递归遍历
        findPath(root.left, target);
        findPath(root.right, target);

        //回退
        list.remove(list.size() - 1);
        return listAll;
    }


    public TreeNode convert(TreeNode root){

        TreeNode lastNode=convertNode(root,null);
        TreeNode pHead=lastNode;
        while(pHead!=null&&pHead.left != null){
            pHead=pHead.left;
        }
        return pHead;
    }
    public TreeNode convertNode(TreeNode root, TreeNode lastNode){

        if(root==null){
            return null;
        }
        TreeNode curr=root;
        if(curr.left!=null){
            lastNode=convertNode(curr.left,lastNode);
        }
        curr.left=lastNode;
        if(lastNode!=null){
            lastNode.right=curr;
        }
        lastNode=curr;
        if(curr.right != null){
            lastNode= convertNode(curr.right, lastNode);
        }
        return lastNode;
    }

    public void main(String[] args) {
        TreeNode trees[] = new TreeNode[20];
        for (int i = 0; i < 9; i++) {
            trees[i] = new TreeNode(i);
        }
        for (int i = 0; i < 3; i++) {
            trees[i].left = trees[3 * i + 1];
            trees[i].right = trees[3 * i + 2];
        }

        ArrayList<Integer> result1 = preOrder(trees[0]);
        ArrayList<Integer> result2 = inOrder(trees[0]);
        int[] pre = new int[result1.size()];
        int[] in = new int[result2.size()];

        for (int i = 0; i < pre.length; i++) {
            pre[i] = result1.get(i);
            in[i] = result2.get(i);
        }

        TreeNode node = reConstructBinaryTree2(pre, in);
        ArrayList<Integer> list = preOrder(node);
        for (int value : list) {
            System.out.println(value);
        }
    }
}
